#include <stdlib.h>
#include <memory.h>

typedef enum { false, true } bool;

bool IsValid(int i, int *s) {
    /* 检查第i个棋子放置是否合法 */
    int j;
    bool ret;

    ret = true; /* 默认合法 */
    for (j = 0; j < i; j++) { /* 对每个在i之前放置的棋子 */
        if (s[j] == s[i]) { /* 如果跟i同列 */
            ret = false; /* 则不合法 */
            break;
        }
        /* 如果跟i同对角线 */
        if ((s[j] - s[i]) == (j - i) || (s[j] - s[i]) == (i - j)) {
            ret = false; /* 则不合法 */
            break;
        }
    }
    return ret;
}

bool BackTracking(int *s, int i, int n) {
    /* 回溯求解，放置第i个棋子 */
    bool result;
    int j;

    result = false;
    if (i == n) { /* (s[0...n-1]均已解决，成功结束 */
        Print(s, n); /* 输出这组解 */
        result = true;
    } else {
        for (j = n - 1; j >= 0; j--) { /* 按列号递减进行尝试 */
            s[i] = j; /* 将第i行的皇后放到第j列 */
            if (IsValid(i, s) == true) { /* 如果这种放置合法 */
                result = BackTracking(s, i + 1, n); /* 继续深度优先搜索 */
                if (result ==
                            false) { /* 说明第i+1个棋子怎么放都不能构成部分解 */
                    s[i] = 0; /* 消除i的影响，回溯到s[0...i-1]状态 */
                }
            }
            if (result == true) { /* 找到一组解 */
                break; /* 终止搜索 */
            }
        } /* 结束对第i个棋子所有放置位置的检查 */
    }
    return result;
}

void Queens(int n) {
    int *s;

    s = (int *)malloc(sizeof(int) * n);
    memset(s, 0, sizeof(int) * n);
    BackTracking(s, 0, n);
    free(s);
}